

let Chart = (function(){

//  存放景点的信息
class Attractions {
  constructor(number, name, Introduction) {
    this.number = number;

    this.name = name;

    this.Introduction = Introduction;
  }
}

// totalPath总路径
// pathIndex  途经景点的下标数组
// pathName  途经景点的名字数组
// pathLength  途经景点的长度数组
class AttractionsAction {
  constructor(totalPath, pathIndex, pathName, pathLength) {
    this.totalPath = totalPath;

    this.pathIndex = pathIndex;

    this.pathName = pathName;

    this.pathLength = pathLength;
  }
}

/**
 *map转换为json
 */
function _strMapToObj(strMap) {
  let obj = Object.create(null);
  for (let [k, v] of strMap) {
    obj[k] = v;
  }
  return obj;
}

// 这里的bug map 的值是数字，转化为 json 再 转回来 会变成字符,需要进行一步处理

/**
 * json 转 map
 */
function _objToStrMap(obj) {
  let strMap = new Map();
  for (let k of Object.keys(obj)) {
    strMap.set(parseInt(k), obj[k]);
  }
  return strMap;
}

window.onbeforeunload = function () {

  // map 不能被序列化 , 所以先使用_strMapToObj 函数转化为 对象
  localStorage.setItem("arr", JSON.stringify(_strMapToObj(_arr)));

  localStorage.setItem("chart", JSON.stringify(_chart));

  localStorage.setItem("frequency",_frequency);

  console.log("保存数据成功");
};

// 用于存放景点的信息

let _arr 

// 用于存放邻接矩阵

let _chart


// 用于存储次数
let _frequency


// 存放景点的图的类
// 实现了一个无向图
class Chart {

  // 初始化邻接矩阵
  // 大小 500*500
  initChart(){

    let arr = [];

    for(let i = 0 ; i< 500 ; i++){

      arr[i] = [];

      for(let j = 0 ; j < 500 ; j++){

        arr[i][j] = 1000000000 ;

      }

    }

    return arr ;

  }


  constructor() {

    //let frequency = null , arr = null , chart = null;

    let frequency = localStorage.getItem("frequency");

    let arr = localStorage.getItem("arr");

    let chart = localStorage.getItem("chart");

   // console.log(arr);

    console.log(frequency);

    if (arr !== null) {
      // 将 json 从 字符串转化为 对象，再转化为 map
      arr = _objToStrMap(JSON.parse(arr));
    }

    if (chart !== null) {
      chart = JSON.parse(chart);
    }

    if (frequency !== null) {
       frequency = Number.parseInt(frequency);
    }

    //console.log(arr);

    // 初始化哈希表，用于存储节点的信息
    _arr = arr || new Map();

    // 初始化图，用于表示景点之间的联系
    // 使用了邻接矩阵
    _chart = chart || this.initChart();

    _frequency = frequency || 0 ;


   // console.log(_chart);

    console.log(_arr)


    // 初始化一部分数据信息
    if(_frequency === 0){

      for(let i = 0 ; i < data.length ; i++){

        _arr.set(data[i].number , new Attractions(data[i].number, data[i].name, data[i].Introduction));

      }

    }

    _frequency++;

  }

  // 存入景点
  saveAttractions(number, name, Introduction) {
    // 先判断景点是否已经存在，再判断景点的下标是否已经被使用

    for (let i of _arr.keys()) {
      if (_arr.get(i).name === name) {
        return -1;
      }
    }

    if (_arr.has(number)) {
      return 0;
    }

    _arr.set(number, new Attractions(number, name, Introduction));

    return 1;
  }

  // 修改编号下的景点信息，同时删除旧的节点对应的chart表信息
  updateAttractions(number, name, Introduction) {
    this.deleteAttractions(number);

    _arr.set(number, new Attractions(number, name, Introduction));
  }

  // 查询景点
  getAttractions(data) {
    // 输入的是要查询景点的编号
    if (typeof data === "number") {
      return _arr.has(data) ? _arr.get(data) : null;
    }

    // 输入的是要查询景点的名称
    if (typeof data === "string") {
      for (let i of _arr.keys()) {
        console.log([i]);

        if (_arr.get(i).name === data) {
          return _arr.get(i);
        }
      }

      return null;
    }
  }

  // 删除景点
  deleteAttractions(data) {
    // 输入的是要查询景点的编号
    // 删除节点并将节点信息返回
    if (typeof data === "number") {
      if (!_arr.has(data)) {
        return false;
      }

      // 把景点的邻接矩阵删除掉
    
      for (let i = 0; i < _chart[data].length; i++) {
          //  console.log(_chart[data][i])

          if (_chart[data][i] !== 1000000000) {
            this.deleteAttractionsContact(data, i);
          }
        }


      return _arr.delete(data);
    }

    // 输入的是要查询景点的名称
     if (typeof data === "string") {
      // 获取要删除的节点下标信息
    let  index = this.attractionNameToSubscript(data);

      if (index === null) {
        return false;
      }

      if (_chart[index] !== null) {
        for (let i = 0; i < _chart[index].length; i++) {
          // console.log(_chart[index][i])

          if (_chart[index][i] !== 1000000000) {
            //   console.log(index, i);

            this.deleteAttractionsContact(index, i);
          }
        }
      }

      return _arr.delete(index);
    }
  }

  // 以数组的形式返回所有景点的信息
  getAllAttractions() {
    let res = [];

    for (let i of _arr.values()) {
      res.push(i);
    }

    return res;
  }

  
  // 根据输入的景点名称，返回景点的下标信息
  attractionNameToSubscript(name){

    for(let i of _arr.keys()){

      if(_arr.get(i).name === name){

        return i;
      }
      
    }

    return null ;

  }


  // 存入景点之间的关联
  // 添加景点的路径和更新景点的路径
  saveAttractionsContact(Attraction1, Attraction2, PathLength) {
   

    _chart[Attraction1][Attraction2] = PathLength;

    _chart[Attraction2][Attraction1] = PathLength;

  }

  // 删除景点之间的路径关系
  deleteAttractionsContact(Attraction1, Attraction2) {
    //  console.log(Attraction1, Attraction2);

    _chart[Attraction1][Attraction2] = 1000000000;

    _chart[Attraction2][Attraction1] = 1000000000;
  }

  //查询两个景点之间的最短路径
  // 使用 dijkstra 算法
  // Attraction1 是起点 ， Attraction2 是 终点
  getShortestPath(Attraction1, Attraction2) {

  
    console.log(Attraction1)

    console.log(Attraction2)



    let pre = new Array(_chart.length); // pre [v] 数组表示从起点到顶点 v 的最短路径上 v 的前一个顶点

    // 用于记录起点到各点的最短路径长度,初始化是无穷大
    let recording = new Array(_chart.length).fill(1000000000);

    let sign = new Array(_chart.length).fill(false); // 标记数组， sign[i] == true 表示已访问。初始值为 false

    

    // n 是当前的顶点数
    let n = _chart.length;

    // 初始化状态设每个点的前驱为自身
    for (let i = 0; i < n; i++) {
      pre[i] = i;
    }

    recording[Attraction1] = 0; // 起点 Attraction1 到达自身的距离是 0

     

    for (let i = 0; i < n; i++) {
      //循环 n 次
    let u = -1;
     
      let MIN = 1000000000; // u 使 recording[u] 最小 ， MIN 存放该最小的 recording[u]

      for (let j = 0; j < n; j++) {
        if (sign[j] === false && recording[j] < MIN) {

          u = j;

          MIN = recording[j];

        }
      }


      // 找不到小于1000000000 的 recording[u] ， 说明剩下的顶点和 起点 Attraction1 不连通

      if (u == -1){

        break ;
      } 

      sign[u] = true;

      for (let v = 0; v < n; v++) {
        // 如果 v 未访问 && u 能到达 v && 以 u 为 中介点 可以使 d[v] 更优

        if (
          sign[v] === false &&
          _chart[u][v] !== 1000000000 &&
          recording[u] + _chart[u][v] < recording[v]
        ) {
          recording[v] = recording[u] + _chart[u][v]; // 优化 recording[v]

          pre[v] = u; // 记录v 的前驱顶点 是 u
        }
      }
    }

    if(recording[Attraction2] === 1000000000){
      return null ;
    }


    let pathIndex = this.getShortPathIndex(pre, Attraction1, Attraction2);

    console.log(pathIndex);

    // totalPath , pathIndex , pathName , pathLength
    return new AttractionsAction(
      recording[Attraction2],
      pathIndex,
      this.pathIndexToPathName(pathIndex),
      this.pathIndexToPathLength(pathIndex)
    );
  }

  // 根据前驱数组，返回每一层的顶点号
  // 使用递归的方式遍历数组
  // 返回最短路径经过的节点

  getShortPathIndex(pre, s, v) {

   // console.log(pre);

    console.log(s)

    console.log(v)

    if (s === v) {
      return [s];
    }

    let arr = [];

    let res = this.getShortPathIndex(pre, s, pre[v]);

    arr = arr.concat(res);

    arr.push(v);

    return arr;
  }



  // 根据景点的下标信息获取景点的名称信息
  pathIndexToPathName(pathIndex) {
    let res = [];

    for (let i of pathIndex) {
      res.push(_arr.get(i).name);
    }

  //  console.log(res)

    return res;
  }

  // 根据景点的下标信息获取具体的路径长度信息
  pathIndexToPathLength(pathIndex) {

    console.log(pathIndex);

   // console.log(_chart);

    let res = [];

    for (let i = 0; i < pathIndex.length - 1; i++) {

      res.push(_chart[pathIndex[i]][pathIndex[i + 1]]);
    }

    return res;
  }

  dfs(sign, data,pre,Attraction1, Attraction2){

  //  console.log(Attraction1)

    if(Attraction1 === Attraction2){

      console.log(pre)

      data.push(pre);

      return ;

    }

    for(let i = 0 ; i < _chart[Attraction1].length ; i++){

      if(_chart[Attraction1][i] !== 1000000000 && sign[i] === false ){

      let res = pre.map((value)=>{ return value})

      res.push(i)

      sign[i] = true ;

      this.dfs(sign,data, res , i , Attraction2);

      sign[i] = false ;

      }
      
    }

  }

  // 获取2个顶点之间的所有距离
  // 使用深度优先搜索实现
  getAllContactPath(Attraction1, Attraction2){

    // console.log(_chart)

    let data = [];

    let sign = new Array(_chart.length).fill(false);

    sign[Attraction1] = true ;

    this.dfs(sign , data,[Attraction1],Attraction1, Attraction2);

    sign[Attraction1] = false ;

    let res = [];


    for(let i = 0 ; i < data.length ; i++){

      let lenthArr = this.pathIndexToPathLength(data[i])

      let length = 0 ;

      for(let i = 0 ; i< lenthArr.length ; i++){

        length += lenthArr[i];
      }

      res.push( new AttractionsAction(
        length,
        data[i],
        this.pathIndexToPathName(data[i]),
        lenthArr
      ))

    }


    console.log(res);

    return res ;

  }


  // 获取所有景点之间的最短路径
  // 使用 floyd 算法
  getAllPath(start) {

    let dis = [];

    let n = _chart.length;  // 求出邻接矩阵的顶点数

    for(let i = 0 ; i< n ; i ++ ){

      dis[i] = [];

    }

    // 初始化所有顶点间的距离都是无穷大

    for(let i = 0 ; i < n ; i++){

      for(let j = 0 ; j < _chart[i].length ; j++){

        dis[i][j] = 1000000000 ;

      }
    }

    // 将顶点到顶点自身的距离是0

    for(let i = 0 ; i < n ; i++){

      dis[i][i] = 0 ;
    }

    // 将chart 表的距离信息复制到 dfs 表上

    for(let i = 0 ; i < n ; i++){

      for(let j = 0 ;j < _chart[i].length ; j++){

        dis[i][j] = _chart[i][j];

      }
    }



    for(let k = 0 ; k < n ; k++){

      for(let i = 0 ;i < n ; i++){

        for(let j = 0 ; j < n ; j++){

          if(dis[i][k] != 1000000000 && dis[k][j] != 1000000000 && dis[i][k] + dis[k][j] < dis[i][j]){

              dis[i][j] = dis[i][k] + dis[k][j]  // 找到更短的路径
          }

        }

      }

    }

   return dis;
    
  }
}

let CHART = new Chart() ; //Chart 类的实例

Object.freeze(CHART);


let res = {

  init: function(){

    return CHART ;

  }


}

Object.freeze(res);

return res ;


})()




